package org.example.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author: lynn
 * @Descript: 三数之和，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组
 * @date: 2021/7/12 8:14
 * @version: 1.0
 */
public class LC15 {

    public static void main(String[] args) {
        int[] nums={-2,0,1,1,2}; // -1 -2 0 1 2 3
        int target =0;
        System.out.println(threeSum(nums));
    }

    /**
     * 排序+双子针，暴力法很容易超时
     * @param nums
     * @solution: https://leetcode-cn.com/problems/3sum/solution/3sumpai-xu-shuang-zhi-zhen-yi-dong-by-jyd/
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res=new ArrayList<>();
        if (nums.length<3||nums==null) return new ArrayList<>();
        Arrays.sort(nums);// 先排序
        for (int k = 0; k <nums.length-2 ; k++) {
            if(nums[k] > 0) break;
            if(k > 0 && nums[k] == nums[k - 1]) continue; //fixme 注意写法
            int l=k+1;
            int r=nums.length-1;
            while (l<r){
                int sum = nums[k] + nums[l] + nums[r];
                if(sum < 0){
                    while(l < r && nums[l] == nums[++l]); // fixme
                } else if (sum > 0) {
                    while(l < r && nums[r] == nums[--r]);
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[l], nums[r])));
                    while(l < r && nums[l] == nums[++l]);
                    while(l < r && nums[r] == nums[--r]);
                }
            }
        }
        return res;
    }
}
